package sortAlgorithm;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {3, 2, 5, 7, 6, 9};
        mergeSort1(a);
        System.out.println(Arrays.toString(a));
    }
    //迭代
    public static void mergeSort1(int[] nums){
        int length = nums.length;
        int[] helper = Arrays.copyOf(nums, length);
        for(int interval = 1; interval < length; interval *= 2){
            for(int start = 0; start < length; start += interval * 2){
                int mid = Math.min(length, start + interval);
                int end = Math.min(length, start + 2 * interval);
                int i = start, j = mid, cur = start;
                while(i < mid || j < end){
                    if(j == end || (i < mid && nums[i] < nums[j])){
                        nums[cur++] = helper[i++];
                    }else{
                        nums[cur++] = helper[j++];
                    }
                }
            }
            helper = Arrays.copyOf(nums, length);
        }
    }
    /**
     * 归并排序
     *
     * @param array 待排数组
     */
    public static void mergeSort(int[] array) {
        mergeSort(array, 0, array.length - 1);
    }

    /**
     * 归并排序
     *
     * @param array 待排数组
     * @param begin 开始下标
     * @param end   结束下标
     */
    private static void mergeSort(int[] array, int begin, int end) {
        if (begin < end) {
            int mid = begin + ((end - begin) >> 1);
            mergeSort(array, begin, mid);
            mergeSort(array, mid + 1, end);
            merge(array, begin, mid, end);
        }
    }

    /**
     * 归并合并
     *
     * @param array 待排数组
     * @param begin 开始下标
     * @param mid   中间下标
     * @param end   结束下标
     */
    private static void merge(int[] array, int begin, int mid, int end) {
        int[] helper = new int[array.length];    //array副本
        int k = 0, current = begin;    //current从begin开始
        for (int i : array) {
            helper[k++] = i;
        }
        int left = begin, right = mid + 1;
        while (left <= mid && right <= end) {
            if (helper[left] <= helper[right]) {
                array[current++] = helper[left++];
            } else {
                array[current++] = helper[right++];
            }
        }
        while (left <= mid) {
            array[current++] = helper[left++];
        }
    }
}
